Bloom Filter

发表于   |  

Bloom Filter简介。

布隆过滤器是用来判断一个元素是否在集合中的数据结构，它使用一系列Hash函数和一个位数组来判断。

首先需要准备一个长度为m的位数组，每一位初始化为0，然后在存元素的时候通过k个Hash函数分别将元素映射到数组的k个位置，并设置为1。之后在判断某一元素是否存在于集合中就只需要判断通过k个Hash函数分别将元素映射到数组的k个位是否都为1，如果不是，那么该元素一定不在集合中，如果是，那么元素有一定概率在集合中，这个概率是多少，取决于m，k和存储在集合中的元素个数n。

Bloom Filter

上图将x,y,z存入集合，将对应的位设为1，然后查询w是否在集合中，由于通过3个Hash函数计算出来的对应位置有一位不为1，则表示w不在集合中。

概率如何计算：Probability of false positives这里讲的比较详细了。

其实我们可以发现如果m越长，n越少，k越多那么误判的几率就越低。

k的选择需要考虑m和n的值，可以详看上面的链接，这里直接给出k取$(\frac mn)ln2$为最佳。

Bloom Filter的时间和空间优势还是挺明显的，相比较HashSet等其他方式来判断是否在集合中，空间上由于Bloom Filter并不存储数据本身，而只用了一个位数组，这能极大的节省空间，时间上面需要通过k个Hash函数，可以认为是常数的复杂度。缺点就是会出现误判，也不支持删除操作。

虽然Bloom Filter通过合理的选择m和k能有效降低误判，但是还是免不了出现误判，所以Bloom Filter适合哪些不要求百分百正确的场景，比如垃圾邮件，黑名单等等。

代码如下（Github地址）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
package io.github.ztmark;

import com.google.common.collect.ImmutableList;
import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;
import java.util.Random;

public class BloomFilter<T> {

    private final BitSet bitSet;
    private final int bitSize;
    private final int expectedNumberOfElements;
    private final ImmutableList<HashFunction> hashFunctions;
    private final int k;
    private int addedNumberOfElements;



    public BloomFilter(int bitSize, int expectedNumberOfElements) {
        if (bitSize <= 0 || expectedNumberOfElements <= 0) {
            throw new RuntimeException("wrong parameters bitSize and expectedNumberOfElements should greater than zero.");
        }
        this.bitSize = bitSize;
        bitSet = new BitSet(bitSize);
        this.expectedNumberOfElements = expectedNumberOfElements;
        // k = m / n * ln2
        k = (int) Math.round(1.0 * bitSize / expectedNumberOfElements * Math.log(2));
        hashFunctions = HashFunctionGenerator.generateKHashFunctions(k);
        addedNumberOfElements = 0;
    }

    public void add(T elem) {
        for (HashFunction function : hashFunctions) {
            bitSet.set(Math.abs(function.hashInt(elem.hashCode()).asInt() / bitSize));
        }
        addedNumberOfElements++;
    }

    public boolean contains(T elem) {
        for (HashFunction function : hashFunctions) {
            if (!bitSet.get(Math.abs(function.hashInt(elem.hashCode()).asInt() / bitSize))) {
                return false;
            }
        }
        return true;
    }

    public double getFalsePositiveProbability() {
        // p = (1 - e^(-k * n / m)) ^ k
        return Math.pow((1 - Math.exp(-k * 1.0 * addedNumberOfElements / bitSize)), k);

    }

    public int getAddedNumberOfElements() {
        return addedNumberOfElements;
    }

    public int getBitSize() {
        return bitSize;
    }

    public int getExpectedNumberOfElements() {
        return expectedNumberOfElements;
    }

    public int getNumberOfHashFunction() {
        return k;
    }

    private static final class HashFunctionGenerator {

        public static HashFunction generateAHashFunction() {
            return Hashing.murmur3_128(new Random(System.currentTimeMillis()).nextInt());
        }

        public static ImmutableList<HashFunction> generateKHashFunctions(int k) {
            Random random = new Random(System.currentTimeMillis());
            List<HashFunction> hashFunctions = new ArrayList<HashFunction>();
            for (int i = 0; i < k; i++) {
                hashFunctions.add(Hashing.murmur3_128(random.nextInt()));
            }
            return ImmutableList.copyOf(hashFunctions);
        }

    }


}